Congruences et opérations

Propriété

Soit \(a , a' , b , b' \in \mathbb{Z}\) et \(n \in \mathbb{N}^\ast\) .

• Si \(a \equiv b \ [n]\) et \(a' \equiv b' \ [n]\) , alors \(a+a' \equiv b+b' \ [n]\) .
  
• Si \(a \equiv b \ [n]\) et \(a' \equiv b' \ [n]\) , alors \(aa' \equiv bb' \ [n]\) .
• Si \(a \equiv b \ [n]\) , alors pour tout \(k \in \mathbb{N}\) , \(a^k \equiv b^k \ [n]\) .
  

Exemples

• Si \(x \equiv 2 \ [7]\) et \(y \equiv 6 \ [7]\) , alors \(x+y \equiv 8 \equiv 1 \ [7]\) .
  
• Si \(x \equiv 2 \ [7]\) et \(y \equiv 6 \ [7]\) , alors \(xy \equiv 12 \equiv 5 \ [7]\) .
  
• Si \(x \equiv 2 \ [7]\) , alors \(x^2 \equiv 4 \ [7]\) et \(x^3 \equiv 8 \equiv 1 \ [7]\) .
  

Démonstration

Dans toute la démonstration, on suppose que \(a \equiv b \ [n]\) et \(a' \equiv b' \ [n]\) .
Ainsi, il existe \(k , k' \in \mathbb{Z}\) tels que \(a-b=kn\) et \(a'-b'=k'n\) .

• On a :
  \(\begin{align*} (a+a')-(b+b') & =a-b+a'-b' \\ & =kn+k'n \\ & =(k+k')n \\ & =k''n \end{align*}\)
  avec  \(k''=k+k' \in \mathbb{Z}\)  .
  Ainsi,  \((a+a')-(b+b')\)  est un multiple de  \(n\)  et donc  \(a+a' \equiv b+b' \ [n]\) .
• On a :
  \(\begin{align*} aa'-bb' & =aa'-ba'+ba'-bb' \\ & =(a-b)a'+b(a'-b') \\ & =kna'+bk'n \\ & =(ka'+bk')n \\ & =k''n \end{align*}\)
  avec \(k''=ka'+bk' \in \mathbb{Z}\) .
  Ainsi, \(aa'-bb'\) est un multiple de \(n\) et donc \(aa' \equiv bb' \ [n]\) .
• Montrons par récurrence que, pour tout \(k \in \mathbb{N}\) , \(a^k \equiv b^k \ [n]\) .
  Initialisation 
  Pour \(k=0\) , on a \(a^0=b^0=1\) et donc \(1 \equiv 1 \ [n]\) .
  Hérédité 
  Soit \(k \in \mathbb{N}\) tel que \(a^k \equiv b^k \ [n]\) .
  Comme \(a \equiv b \ [n]\) et \(a^k \equiv b^k \ [n]\) , en utilisant la propriété du produit :
  \(a \times a^k \equiv b \times b^k \ [n]\)  c'est-à-dire \(a^{k+1} \equiv b^{k+1} \ [n]\) .
  Conclusion 
  Pour tout \(k \in \mathbb{N}\) , \(a^k \equiv b^k \ [n]\) .